package leetcode_day._2021._202112._0110;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/12/7 12:19
 * 边界着色
 * 颜色相同，并且“连在”一起的方块，我们称为连通分量，这个“连在”表示的是上下左右直接相连，而斜着的那种对角线的相连不算
 * 边界：方块本身就在m*n这个矩阵的边界上；方块周围存在着和自己颜色不同的方块
 * 使用指定颜色 color 为所有包含网格块 grid[row][col] 的连通分量的边界进行着色，并返回最终的网格 grid 。
 * 算法：广度优先搜索
 */
public class _07_1034 {

    public int[][] colorBorder(int[][] grid, int row, int col, int color) {
        int m = grid.length, n = grid[0].length;
        int[][] ans = new int[m][n];
        int[][] dirs = new int[][]{{0, 1}, {1, 0}, {0, -1}, {-1, 0}};
        Deque<int[]> queue = new ArrayDeque<>();
        queue.addLast(new int[]{row, col});
        while (!queue.isEmpty()) {
            int[] poll = queue.pollFirst();
            int x = poll[0], y = poll[1], cnt = 0;
            for (int [] dir : dirs) {
                int nx = x + dir[0], ny = y + dir[1];
                if (nx < 0 || nx > m || ny < 0 || ny > n) continue;
                if (grid[x][y] != grid[nx][ny]) continue;
                else cnt++;
                if (ans[nx][ny] != 0) continue;
                queue.addLast(new int[]{nx, ny});
            }
            ans[x][y] = cnt == 4 ? grid[x][y] : color;
        }
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) if (ans[i][j] == 0) ans[i][j] = grid[i][j];
        }
        return ans;
    }

}
